#include<iostream>

#include<string>

#include"HashMap.h"


void MaxHeap(std::string& s, int n, int i)
{
    int left = 2*i+1;
    int right = 2*i+2;
    int max = i;
  
    if(left < n && s[left] > s[max])
    {
        max = left;
    }
  
    if(right < n && s[right] > s[max])
    {
        max = right;
    }
  
    if(max != i)
    {
        std::swap(s[i],s[max]);
        MaxHeap(s,n,max);
    }
}

//堆排
void Sort(std::string& s)
{
    int n = s.size();
    
    for(int i = n /2 -1; i>=0;i--)
    {
        MaxHeap(s,n,i);
    }
    
    for(int i=n-1;i>=0;i--)
    {
        std::swap(s[0],s[i]);
       
        MaxHeap(s,i,0);
    }

}


int main()
{
    //字母异位词 eat ate

    HashMap m(100);


    // m.Insert("zhangsan",100);
    // m.Insert("lisi",90);
    // m.Insert("wangwu",80);

    // m.show();




    // std::cout<<*m.Get("wangwu")<<std::endl;

    // m["zahngsan"] = 100;
    // m["lisi"] = 90;
    // m["wangwu"] = 80;
    // m["zhaoliu"] = 70;


    
    // m.show();

    // m.Remove("wangwu");
    // m.show();

    //按照字母异位词分组
    std::string s[] = {"eat","ate","tan","tea","nat","bat"};

     
    // std::string s ="zhangsan";
    // Sort(s);
    // std::cout<<s<<std::endl;

    for(int i=0;i<6;i++)
    {
        std::string temp = s[i];
        Sort(temp);
        m.Insert(temp,s[i]);
    }

    // m.show();
    m.ShowByGroup();

    return 0;
}